/* 338. 比特位计数 */
/**
 * @param {number} n
 * @return {number[]}
 */
/* 暴力 */
var countBits = function (n) {
    const result = Array.from({ length: n + 1 }).fill(0)
    for (let i = 0; i <= n; i++) {
        result[i] = countOnes(i)
    }
    return result
};
var countOnes = (x) => {
    let ones = 0
    /* 
        将二进制表示的最后一个1变成0
        统计某个二进制数里面1的个数
    */
    while (x > 0) {
        x &= x - 1
        ones++
    }
    return ones
}
/* 动态规划:最高有效位 */
var countBits = function (n) {
    const bits = new Array(n + 1).fill(0)
    let highBit = 0
    for (let i = 1; i <= n; i++) {
        /* 
          判断是否是2 的整数次幂:  i & (i - 1) == 0
        */
        if ((i & (i - 1)) == 0) {
            // 更新当前最高有效位
            highBit = i
        }
        bits[i] = bits[i - highBit] + 1
    }
}
/* 
    动态规划:最低有效位 
    对于正整数x，将其二进制表示右移一位，等价于将其二进制表示的最低有效位去掉，得到的数是|x/2|
    如果bit|x/2|的值已知,则可以得到bit[x]
    奇数: bit[x] = bit[x/2] + 1
    偶数: bit[x] = bit[x/2]
*/
var countBits = function (n) {
    const bits = new Array(n + 1).fill(0)
    for (let i = 1; i <= n; i++) {
        bits[i] = bits[i >> 1] + (i & 1)
    }
    return bits
}
/* 
    动态规划:最低设置位 
*/
var countBits = function (n) {
    const bits = new Array(n + 1).fill(0)
    for (let i = 1; i <= n; i++) {
        /* 将 i 的最低设置位从1变成0 */
        bits[i] = bits[i & (i - 1)] + 1
    }
    return bits
}


countBits(2)